{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://cs229.stanford.edu/ps/ps2/ps2.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $\\theta$ is of too high a dimension to be written explicit, it will always be represented in the form of $K(\\theta, \\phi(x))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (b)\n",
    "\n",
    "To do a prediction, \n",
    "\n",
    "\\begin{align*}\n",
    "h_{\\theta^{(i)}}(x^{(i + 1)}) &= g((\\theta^{(i)})^T \\phi(x^{(i + 1)})) \\\\\n",
    "                      &= g(K(\\theta^{(i)}, \\phi(x^{(i + 1)}))\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# (c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equivalent to \n",
    "\n",
    "\\begin{align*}\n",
    "\\theta^{(i+1)} &:= \\begin{cases}\n",
    "  \\theta^{(i)} + \\alpha y^{(i+1)} \\phi(x^{(i+1)})          & \\text{if} \\; h_{\\theta^{(i)}}\\big(\\phi (x^{(i+1)})\\big) y^{(i+1)} <0 \\\\\n",
    "  \\theta^{(i)}    & \\text{otherwise}\n",
    "\\end{cases} \\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We could update $K \\big(\\theta^{(i+1)}, \\phi(x^{(i + 1)}) \\big)$ directly. Dot product both sides by $\\phi(x^{(i+1)})$,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*}\n",
    "K(\\theta^{(i+1)}, \\phi(x^{(i+1)})) &:= \\begin{cases}\n",
    "  K(\\theta^{(i)}, \\phi(x^{(i + 1)})) + \\alpha y^{(i+1)} K\\big(\\phi(x^{(i+1)}), \\phi(x^{(i+1)})\\big)          & \\text{if} \\; K\\big(\\theta^{(i)}, \\phi(x^{(i+1)}) \\big) y^{(i+1)} <0 \\\\\n",
    "  K(\\theta^{(i)}, \\phi(x^{(i+ 1)}))    & \\text{otherwise}\n",
    "\\end{cases} \\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore, given that there is no need to compute either $\\theta^{(i)}$ or $\\phi(x^{(i)})$ explicity, and only their dot product in kernel form is ever needed, this perceptron algorithm is considered kernelized."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
